# 每次相邻的两个元素逐一进行比较，较大的那个放后面，然后比较下一组


# [6, 2, 1, 3, 5, 4]
# [2, 6, 1, 3, 5, 4]
# [2, 1, 6, 3, 5, 4]
# [2, 1, 3, 6, 5, 4]
# [2, 1, 3, 5, 6, 4]
# [2, 1, 3, 5, 4, 6]
# [1, 2, 3, 5, 4, 6]
# [1, 2, 3, 5, 4, 6]
# [1, 2, 3, 5, 4, 6]
# [1, 2, 3, 4, 5, 6]


def bubble_sort(li: list) -> list:
    """
    冒泡排序, O(n2)
    :param li:
    :return:
    """
    for i in range(len(li) - 1):  # 外层第几次循环挪数
        k = 0
        for j in range(len(li) - 1 - i):  # 每次挪数时依次挪第几位
            if li[j] > li[j+1]:
                # 交换位置
                # tmp = li[j]
                # li[j] = li[j+1]
                # li[j+1] = tmp
                li[j], li[j+1] = li[j+1], li[j]
                k +=1
        if k == 0:
            break
    return li
